/**
 *    Copyright (C) 2008, 2009  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef __CUBEFS_CORE_BTREE_ITERATOR_WALK_H
#define __CUBEFS_CORE_BTREE_ITERATOR_WALK_H

#include <iostream>

#include <cubefs/api/types.hpp>
#include <cubefs/core/container/container.hpp>
#include <cubefs/core/btree/names.hpp>


namespace cubefs    {
namespace ctr       {

using namespace cubefs::btree;


CUBEFS_ITERATOR_PART_BEGIN(IteratorWalkName)

    enum {STEP_UP, STEP_DOWN, STEP_BREAK};


    typedef typename Base::NodeBase                                             NodeBase;


    template <typename Walker>
    NodeBase* __get_from_index_fw(NodeBase *index0, Int &idx, Walker &walker, const bool is_down, bool &down) {
        int step_type = STEP_UP;
        down = false;
        while (step_type != STEP_BREAK) {
            Int c, stop = me_.GetChildrenCount(index0);

            for (c = idx; c < stop; c++) {
                if (!walker(index0, c)) {
                    if (index0->is_leaf()) {
                        step_type = STEP_BREAK;
                        idx = c;
                    }
                    else {
                        step_type = STEP_DOWN;
                    }

                    goto nextStep;
                }
            }

            nextStep:
            if (step_type == STEP_UP) {
                if (index0->is_root()) {
                    if (is_down) {
                        down = true;
                        while (!index0->is_leaf()) {
                            index0 = me_.GetLastChild(index0);
                        }
                        idx = me_.GetChildrenCount(index0) - 1;
                    }
                    else {
                        index0 = NULL; // nothing is found
                        idx = -1;
                    }

                    break;
                }
                else {
                    NodeBase *parent = me_.GetParent(index0);
                    idx = index0->parent_idx() + 1;
                    index0 = parent;
                }
            }
            else if (step_type == STEP_DOWN) {
                index0 = me_.GetChild(index0, c);
                idx = 0;
            }
        }

        return index0;
    }

    template <typename Walker>
    NodeBase* __get_from_index_bw(NodeBase *index0, Int &idx, Walker &walker, const bool is_down, bool &down) {
        int step_type = STEP_UP;

        while (step_type != STEP_BREAK) {
            Int c = idx;
            for (Int c = idx; c >= 0; c--) {
                if (!walker(index0, c)) {
                    if (index0->is_leaf()) {
                        step_type = STEP_BREAK;
                        idx = c;
                    }
                    else {
                        step_type = STEP_DOWN;
                    }

                    goto nextStep;
                }
            }

            nextStep:
            if (step_type == STEP_UP) {
                if (index0->is_root()){
                    if (is_down) {
                        down = true;
                        while (!index0->is_leaf()) {
                            index0 = me_.GetChild(index0, 0);
                        }
                        idx= 0;
                        step_type = STEP_BREAK;
                    }
                    else {
                        index0 = NULL; // nothing is found
                        idx = -1;
                    }
                }
                else {
                    NodeBase *parent = me_.GetParent(index0);
                    idx = index0->parent_idx() - 1;
                    index0 = parent;
                }
            }
            else if (step_type == STEP_DOWN) {
                index0 = me_.GetChild(index0, c);
                idx = me_.GetChildrenCount(index0) - 1;
            }
        }

        return index0;
    }
    
CUBEFS_ITERATOR_PART_END

}
}

#endif //__CUBEFS_CORE_BTREE_ITERATOR_WALK_H
